package com.cdy.demo.algorithm;

import java.util.ArrayList;
import java.util.List;

public class Leetcode1143 {

	public static void main(String[] args) {
		Leetcode1143 Leetcode5 = new Leetcode1143();
	}

	public int longestCommonSubsequence(String text1, String text2) {
		int len = text1.length();
		int len2 = text2.length();
		if (len == 0 || len2 == 0) {
			return 0;
		}
		int[][] dp = new int[len + 1][len2 + 1];
		for (int i = 0; i < len + 1; i++) {
			dp[i][0] = 0;
		}
		for (int i = 0; i < len2 + 1; i++) {
			dp[0][i]=0;
		}

		for (int i = 1; i < len+1; i++) {
			char c1 = text1.charAt(i - 1);
			for (int j = 1; j < len2+1; j++) {
				char c2 = text2.charAt(j-1);
				if (c1 == c2) {
					dp[i][j] = dp[i - 1][j - 1]+1;
				} else {
					dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
				}
			}
		}
		return dp[len][len2];

	}
}
